package top.humbleyuan.linkedlist;

import top.humbleyuan.datastructure.linkedlist.LinkNode;
import top.humbleyuan.datastructure.linkedlist.NormalBothWayNode;
import top.humbleyuan.datastructure.tree.TreeNode;

/**
 * @Author: yuanhuanghui
 * @Date: 2020-08-16
 * @Time: 19:53
 * @Description: 平衡二叉树转双向链表
 */
public class LeetCode_STO_36 {
    public static void main(String[] args) {
        // 暂时没有构造数据
        NormalBothWayNode root = new NormalBothWayNode();
        root.right = new NormalBothWayNode();
        formBTree(root.right);
        NormalBothWayNode res = treeToDoublyList(root.right);
        System.out.println();
    }

    public static void formBTree(NormalBothWayNode tree) {
        tree.val = 4;
        tree.left = new NormalBothWayNode(2);
        tree.left.left = new NormalBothWayNode(1);
        tree.left.right = new NormalBothWayNode(3);
        tree.right = new NormalBothWayNode(5);
    }

    /**
     考虑最终要将头尾节点间关系链接：
     于是最终需要记录头结点和尾结点
     可以考虑保存一个head和pre
     注意头不是原来的头结点了
     **/
    static NormalBothWayNode head = null, pre = null;
    public static NormalBothWayNode treeToDoublyList(NormalBothWayNode root) {
        if(root == null) {
            return root;
        }
        // 中序序遍历
        dfs(root);

        // 链接头尾
        head.left = pre;
        pre.right = head;
        return head;
    }


    public static void dfs(NormalBothWayNode temp) {
        if(temp == null) {
            return;
        }
        dfs(temp.left);

        // 判断pre是否为Null,为null表示当前还在头结点
        if(pre != null) {
            pre.right = temp;
        } else {
            head = temp;
        }
        temp.left = pre;
        pre = temp;

        dfs(temp.right);
    }
}
